package main

import "fmt"

func lengthOfLIS(nums []int) int {
	n := len(nums)
	if n <= 1 {
		return n
	}
	dp := make([]int, n)

	for i := 0; i < n; i++ {
		m := 0
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				m = Max(m, dp[j])
			}
		}
		dp[i] = m + 1
	}

	return MaxInArray(dp)
}

func MaxInArray(x []int) int {
	if len(x) == 0 {
		return 0
	}
	maxVal := x[0]
	for _, v := range x {
		maxVal = Max(maxVal, v)
	}
	return maxVal
}

func Max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func main() {
	s := lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18})
	fmt.Println(s)
}
